def solution(m: int, n: int, a: list):
    assert m == len(a) and all(len(v) == n for v in a)

    vis = [[0 for _ in range(n)] for _ in range(m)]

    def dfs(x, y, k):
        ans = 0
        for (nx, ny) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if nx < 0 or ny < 0 or nx >= m or ny >= n or vis[nx][ny] or k == 0 and a[nx][ny] <= a[x][y] or k == 1 and \
                    a[nx][ny] >= a[x][y]:
                continue
            vis[x][y] = 1
            ans = max(ans, dfs(nx, ny, k ^ 1) + 1)
            vis[x][y] = 0
        return ans

    res = 0
    for i in range(m):
        for j in range(n):
            res = max(res, dfs(i, j, 0), dfs(i, j, 1))
    return res


if __name__ == '__main__':
    print(solution(m = 2, n = 2, a = [[1, 2], [4, 3]]) == 3)
    print(solution(m = 3, n = 3, a = [[10, 1, 6], [5, 9, 3], [7, 2, 4]]) == 8)
    print(solution(m = 4, n = 4, a = [[8, 3, 2, 1], [4, 7, 6, 5], [12, 11, 10, 9], [16, 15, 14, 13]]) == 11)
